import common.ListNode;

/**
 * 86. Partition List 分隔链表
 * https://leetcode-cn.com/problems/partition-list/
 */
class PartionList {
    /**
     * 方法：将链表分割成两部分，小于x的节点在前，大于等于x的节点在后，并保持原有的相对顺序
     *      使用双指针分别连接小于x和大于等于x的节点
     * 
     * Args:
     *   head: 链表头节点
     *   x: 分割的基准值
     * 
     * Returns:
     *   分割后的新链表头节点
     * 
     * Time: O(n)，其中n为链表长度，需要遍历一次链表
     * 
     * Space: O(1)，只使用了常数个额外指针
     */
    public ListNode partition(ListNode head, int x) {
        ListNode smlDummy = new ListNode(0), bigDummy = new ListNode(0);
        ListNode sml = smlDummy, big = bigDummy;
        while(head != null){
            if(head.val < x){
                sml.next = head;
                sml = sml.next;
            }else{
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        sml.next = bigDummy.next;
        big.next = null;
        return smlDummy.next;
    }
}